package com.zjsru.leetcode75.level1;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: cookLee
 * @Date: 2023-11-26
 * 组合总和 III
 * 只使用数字1到9
 * 每个数字 最多使用一次
 */
public class CombinationSum3 {

    /**
     * 主
     * \
     * 输入: k = 3, n = 7
     * 输出: [[1,2,4]]
     * 解释:
     * 1 + 2 + 4 = 7
     * 没有其他符合的组合了。
     * \
     * 输入: k = 3, n = 9
     * 输出: [[1,2,6], [1,3,5], [2,3,4]]
     * 解释:
     * 1 + 2 + 6 = 9
     * 1 + 3 + 5 = 9
     * 2 + 3 + 4 = 9
     * 没有其他符合的组合了。
     * \
     * 输入: k = 4, n = 1
     * 输出: []
     * 解释: 不存在有效的组合。
     * 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
     * \
     * @param args args
     */
    public static void main(String[] args) {
        CombinationSum3 combinationSum3 = new CombinationSum3();
        int k = 3, n = 7;
        System.out.println(combinationSum3.combinationSum3(k, n));
    }

    List<List<Integer>> combinations = new ArrayList<>();
    List<Integer> combination = new ArrayList<>();

    /**
     * 组合sum3:回溯
     *
     * @param k k
     * @param n n
     * @return {@link List}<{@link List}<{@link Integer}>>
     */
    public List<List<Integer>> combinationSum3(int k, int n) {
        //从数字1-9开始
        this.helper(1, 9, k, n);
        return this.combinations;
    }

    /**
     * 帮手：回溯助手类
     *
     * @param k       k
     * @param n       n
     * @param sum     索引
     * @param current 电流
     */
    private void helper(int current, int n, int k, int sum ) {
        //k代表位数判断
        if (this.combination.size() + (n - current + 1) < k || this.combination.size() > k) {
            return;
        }
        if (this.combination.size() == k) {
            int temp = 0;
            //获取当前元素节点下元素的和是否满足n
            for (int num : this.combination) {
                temp += num;
            }
            //满足要求加入集合中
            if (temp == sum) {
                this.combinations.add(new ArrayList<>(this.combination));
                return;
            }
        }
        //增加当前元素来看看是否能满足要求
        this.combination.add(current);
        //增加元素后再次进行递归
        this.helper(current + 1, n, k, sum);
        //移除了最后添加的数字，撤销了前面的添加的元素。因为在后续的递归调用中，探索不包含当前数字的组合。即按照最后数字不同来遍历结果
        this.combination.remove(this.combination.size() - 1);
        //再次进行递归查看
        this.helper(current + 1, n, k, sum);
    }


    /**
     * 帮手2: 剪枝
     * this.helper(n,k,1,0);
     * @param targetSum  目标金额
     * @param k          k
     * @param startIndex 起始索引
     * @param sum        总金额
     */
    public void helper2(int targetSum, int k, int startIndex, int sum) {
        if (sum > targetSum) {
            return;
        }
        if (combination.size() == k) {
            if (sum == targetSum) {
                combinations.add(new ArrayList<>(combination));
            }
            return;
        }
        // 减枝 9 - (k - path.size()) + 1
        for (int i = startIndex; i <= 9 - (k - combination.size()) + 1; i++) {
            combination.add(i);
            sum += i;
            this.helper2(targetSum, k, i + 1, sum);
            //回溯
            combination.remove(combination.size() - 1);
            //回溯
            sum -= i;
        }
    }

}
